package 贪心算法;

public class 加油站 {

    //巧妙解法
    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        int min = Integer.MAX_VALUE;
        int minndex = 0;
        int pre = 0;
        int length = gas.length;
        for (int i = 0; i < length; i++) {
            pre += gas[i] - cost[i];
            if (pre < min){
                min = pre;
                minndex = i;
            }
        }
        return pre < 0? -1: (minndex + 1) % length;
    }

    //暴力解法优化
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            int pre = gas[i];
            while (pre >= cost[j]){
               pre += gas[(j+1)%n] - cost[j];
               j = (j+1)%n;
               if (j == i){
                  return i;
               }
            }
            if (j< i){
                return -1;
            }
            i = j;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] gas ={2,3,4};
        int[] cost ={4,4,2};
        System.out.println(canCompleteCircuit(gas, cost));
    }
}
